/**
 * 我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符，并返回唯一字符的个数。
 *
 * 例如：s = "LEETCODE" ，则其中 "L", "T","C","O","D" 都是唯一字符，因为它们只出现一次，所以 countUniqueChars(s) = 5 。
 *
 * 本题将会给你一个字符串 s ，我们需要返回 countUniqueChars(t) 的总和，其中 t 是 s 的子字符串。输入用例保证返回值为32 位整数。
 *
 * 注意，某些子字符串可能是重复的，但你统计时也必须算上这些重复的子字符串（也就是说，你必须统计 s 的所有子字符串中的唯一字符）。
 *
 *
 *
 * 链接：https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string
 *题解链接：https://leetcode.cn/problems/count-unique-characters-of-all-substrings-of-a-given-string/solution/tong-ji-zi-chuan-zhong-de-wei-yi-zi-fu-b-ajio/
 * 思路：数学
 * 题外：本题千万不要被countUniqueChars这个函数误导，为了优化这个方法想了好久才发现不需要实现这个方法。
 * 思路：想要计算子串中唯一字符，我们可以计算每个字符的贡献值，然后相加即可。
 * 为了计算某个字符的贡献值，我们需要找到它的前相同一个字符的位置lastIndex和后一个相同字符的位置nextIndex，然后计算他对lastIndex + 1到nextIndex - 1这个子串的贡献值。然后我们遍历整个字符串，计算所有字符的贡献值累加即可。
 *举个例子“ABCADEFA主串（此时last是第一个A的下标，cur是第二个A的下标，next是第三个A的下标）
 * 在“BCADEF"子串中，
 * A的左边可以分解为：BCA,CA,A三个子串
 * A的右边可以分解为：空串，D，DE,DEF四个子串
 *因此此时A对于子串的贡献值为：3*4=12
 * 因此对于单个字符来说，它的贡献值计算为（curIndex-lastIndex)*(nextIndex-curIndex)
 */
class UniqueLetterString {
    public int uniqueLetterString(String s) {
        Map<Character,List<Integer>> map=new HashMap<>();
        int len=s.length();
        for(int i=0;i<len;i++) {
            char c=s.charAt(i);
            if(!map.containsKey(c)) {
                map.put(c,new ArrayList<Integer>());
                map.get(c).add(-1);
            }
            map.get(c).add(i);
        }
        int count=0;
        for(Map.Entry<Character,List<Integer>> entry:map.entrySet()) {
            List<Integer> ret=entry.getValue();
            ret.add(len);
            for(int i=1;i<ret.size()-1;i++) {
                count=count+(ret.get(i)-ret.get(i-1))*(ret.get(i+1)-ret.get(i));
            }
        }
        return count;
    }
}